Computer graphics systems have been widely used by designers to design objects such as cars, airplanes, tooling, and the like. In recent years, computer graphics systems have been applied to more and more complex jobs. The objects rendered have improved from the early vector displays to photorealistic images.
Computer graphic systems typically employ what is known as primitives to create and display user specified geometric structures. Typical two-dimensional structures are points, lines, circles, and polygons.
Three-dimensional objects are often represented in polyhedra form. Polyhedra, by definition are, three-dimensional solids formed by a set of polygons. Curved surfaces of three-dimensional objects are typically approximated by displaying a combination of many small polygons.
Typically, designers only want to view a portion of the object. To avoid the rendering problems and clutter inherent in displaying data that is not within the prescribed visible range, graphic systems utilize what is known as a "view clipping" feature. This view clipping feature allows a designer to define a "window" in which a portion of the object is rendered. View clipping is performed using two-dimensional polygon clippers, such as the Sutherland-Hodgman (Sutherland et al,. "Reentrant Polygon Clipping", Communications of the ACM 17:32-42 (1974)) and the Weiler-Atherton (Weiler et al., "Hidden Surface Removal Using Polygon Area Sorting", Computer Graphics 11:214-222 (1977)) methods. These two dimensional clippers clip the two or three dimensional object against the defined window.
In contrast to view clipping, designers often want to inspect their designs (objects) from within. This is typically known as "sectioning." To accomplish this task, some computer graphics systems typically allow the designer to define arbitrary planes about the objects. The intersection of the planes with themselves and the object produce cut-away views which expose the interior of the object. Sectioning is a powerful tool for the graphics system designer.
Additionally, designers often want to determine prior to initiation of the manufacturing process, whether two objects will intersect during assembly and/or operation. In one situation for example, a designer of an airplane may want to ensure that a wheel sub-assembly can be properly be retracted into the airplane housing without interference with the other airplane sub-assemblies. In another situation, the designer may want to know if a cover will mate properly with a housing.
Identification of an interference between two or more objects that operate within the same system and/or subsystem prior to manufacturing is invaluable. As manufacturing costs continue to increase, there is a need for the designer to inspect the operation of their designs prior to entering the manufacturing stage.
One conventional interference system, used in the field of Constructive Solids Geometry (CSG), checks an entire model in three-dimensional space for interference problems. Although such a test is very thorough, it takes a great deal of computational time to render an answer.